package com.sam.book.tree

import com.sam.book.tree.BinarySearchTree.BinaryNode

fun main() {
    print(BSTConvertArray().array2binaryNode(intArrayOf(0,1,2,3,4,5)))
}
/**
 * 有序数组和二叉查找树（搜索二叉树）互转
 * [BinarySearchTree]
 *
 */
class BSTConvertArray {

    fun array2binarySearchTree(array: IntArray): BinarySearchTree<Int>? {
        if (array.isEmpty()) {
            return null
        }
        val tree = BinarySearchTree<Int>()
        for (i in array) {
            tree.insert(i)
        }
        return tree
    }


    /**
     * 有序数据转搜索二叉树
     */
    fun array2binaryNode(array: IntArray): BinaryNode<Int>? {
        return array2binaryNode(array, 0, array.size - 1)
    }

    private fun array2binaryNode(array: IntArray, start: Int, end: Int): BinaryNode<Int>? {
        if (start > end) {
            return null
        }
        val mid = (start + end) / 2
        val root = BinaryNode(array[mid])
        root.left = array2binaryNode(array, start, mid - 1)
        root.right = array2binaryNode(array, mid + 1 , end)
        return root
    }


}